Алгоритам генерисања лавиринта

Алгоритми генерисања лавиринта су аутоматизовани методи за креирање лавиринта.

Методи засновани на теорији графова

Лавиринт може бити генерисан помоћу раније одређеног распореда ћелија (најчешће је то правоугаона мрежа, али су могући и други распореди) са пољима која представљају зид, а налазе се између њих. Овакав, раније генерисан, распоред се може сматрати као повезани граф са страницама које представљају могућа поља за зидове и чворовима који представљају ћелије. Циљем алгоритма за генерисање лавиринта се онда може сматрати прављење подграфа у ком је изазов наћи пут између два одређена чвора.

Ако подграф није повезан, онда постоје делови графа који су изгубљени, јер они не спадају у простор претраге. Ако граф садржи петље тада може постојати више различитих путева између изабраних чворова. Због овога, генерисању лавиринта се најчешће приступа генерисањем насумичног разапињућег стабла. Петље које могу да збуне наивне решаваче лавиринта се могу добити додавањем насумичних ивица у резултујући лавиринт за време извршавања.

Претрага у дубину

Анимација генерисања лавиринта димензије 30 са 20 коришћењем претраге у дубину.

Овај алгоритам је случајна варијанта алгоритма претраге у дубину. Често имплементиран преко стека, овај приступ је један од најједноставнијих начина да се лавиринт генерише путем рачунара. Сматрајмо да је простор за лавиринт велика мрежа ћелија (као велика шаховска табла), где свака ћелија стартује са четири зида. Почећи од насумичне ћелије, рачунар селектује случајну суседну ћелију која још није посећена. Рачунар уклања зид између ове две ћелије и додаје нову ћелију на стек (ово је аналогно цртанју линије по поду лавиринта). Рачунар наставља са овим процесом, а ћелија која нема непосећених суседа се сматра ћорсокаком. Када се нађе у ћорсокаку, он се враћа по путањи док не наиђе на ћелију која има непосећених суседа, а онда наставља генерисање тако што посећује ту непосећену ћелију. Овај процес се понавља док се не посете све ћелије, што узрокује да рачунар уради повратак кроз цео лавиринт до почетне ћелије. Овај приступ гарантује да је простор лавиринта у потпуности посећен.

Као што је већ речено, алгоритам је веома једноставан и не производи претешке лавиринте. Нека специфична унапређења алгоритма могу помоћи да се генеришу лавиринти које је теже решити.

Почети у некој ћелији и назвати је „излаз“.
Означити тренутну ћелију као посећену и узети листу њених суседа. За сваког суседа, почевши од случајно изабраног урадити:
1. Ако тај сусед није био посећен, уклонити зид између те ћелије и тог суседа, и поновити поступак рекурзивно за суседну ћелију.

Као што је раније наведено, овај алгоритам користи дубоку рекурзију која може проузроковати проблеме везане за прекорачење стека на неким рачунарским архитектурама. Алгоритам се може преправити у петљу, чувањем повратних информација у самом лавиринту. Ово такође омогућава брз начин да се прикаже решење, полазећи од било које тачке повратком до излаза.

Лавиринти генерисани претрагом у дубину имају мали фактор гранања и садрже много дугачких путања, што чини претрагу у дубину добрим алгоритмом за генерисање лавирината у видео играма. Случајним уклањањем одређеног броја зидова након креирања лавиринта методом претраге у дубину може се постићи ефекат проширења ходника лавиринта, што може бити одговарајући метод ако тежина решавања лавиринта није од пресудне важности. Овај метод се такође користи у видео играма.

У лавиринтима генерисаним овим алгоритмом, биће релативно лако наћи пут до квадрата који је пробран на почетку алгоритма, јер већина путања води директно до њега, али је зато тешко пронаћи пут назад.

Рекурзивна анализа наниже

Алгоритам претраге у дубину је често имплементиран коришћењем анализе наниже.

Поставити почетну ћелију на текућу и означити је као посећену.
Док постоје непосећене ћелије:
1. Ако текућа ћелија има суседе који нису посећени:
  1. Одабрати случајно једног од непосећених суседа.
  2. Поставити тренутну ћелију на врх стека.
  3. Уклонити зид између текуће и изабране ћелије.
  4. Поставити одабрану ћелију на тренутну ћелију и означити је као посећену.
2. У супротном, ако стек није празан:
  1. Скинути ћелију са стека.
  2. Поставити је да буде текућа ћелија.
3. У супротном:
  1. Узети случајну непосећену ћелију, поставити је на текућу и означити као посећену.

Случајни Крускалов алгоритам

Овај алгоритам је случајна верзија стандардног Крускаловог алгоритма:

Креирати листу свих зидова и креирати сет за сваку ћелију, где сваки сет садржи само по ту једну ћелију.
За сваки зид, у неком случајном редоследу:
1. Ако ћелије подељене овим зидом припадају различитим сетовима:
  1. Уклонити текући зид
  2. Спојити сетове претходно подељених ћелија

Постоји неколико структура података које се могу користити да моделују сет ћелија. Ефикасна имплементација која користи структуру раздвојених сетова може да изврши сваку унију и нађе операцију над два сета у скоро константном времену (прецизније, $O(\alpha (V))$ time; $\alpha (x)<5$ за сваку могућу вредност $x$ ), па је време извршавања овог алгоритма пропорционално броју зидова које лавиринт може да користи.

Питање је само да ли се листа зидова иницијално случајно генерише, или је зид случајно пробран из листе која није случајно генерисана.

Пошто је ефекат овог алгоритма да произведе минимално разапињуће стабло из графа у ком су све гране исте тежине, он тежи да произведе тачне шаблоне који су генерално лако решиви.

Случајни Примов алгоритам

Анимација генерисања лавиринта димензије 30 са 20 коришћењем Примовог алгоритма.

Овај алгоритам је случајна верзија Примовог алгоритма.

Почети са мрежом попуњеном зидовима.
Одабрати ћелију, обележити је као део лавиринта. Додати зидове ћелије у листу зидова.
Док постоје зидови у листи:
1. Узети случајан зид из листе. Ако ћелија на супротној страни није у лавиринту још увек:
  1. Направити од зида пролаз и обележити ћелију на супротној страни као део лавиринта.
  2. Додати суседне зидове ћелије у листу зидова.
2. Ако је ћелија на супротној страни већ била у лавиринту, уклонити зид из листе.

Као у алгоритму претраге у дубину, обично ће бити релативно лако пронаћи пут до почетне ћелије, али тешко пронаћи пут било где друго.

Једноставно покретање класичног Примовог алгоритма на граф са случајним вредностима тежина грана производи лавиринт стилски идентичан оном који креира Крускалов алгоритам, зато што су и један и други алгоритам засновани на минималном разапињућем стаблу. Уместо тога, овај алгоритам уводи стилску варијацију, јер ивице ближе почетној тачки имају нижу ефективну тежину.

Модификована верзија

Иако класични Примов алгоритам чува листу ивица, за генерисање лавиринта можемо уместо тога да одржавамо листу суседних ћелија. Ако случајно изабрана ћелија има више ивица које је повезују са постојећим лавиринтом, треба пробрати неку од ових ивица на случајан начин. Овакав приступ ће да тежи да разграна лавиринт мало више него горња верзија, заснована на ивицама.

Метода рекурзивне поделе

Лавиринти могу бити креирани и рекурзивном поделом, алгоритмом који ради на следећи начин:

Почети са простором за лавиринт без зидова. Ово ћемо назвати дворана.
Поделити дворану случајно постављеним зидом (или више њих) где сваки зид садржи случајно позициониран пролаз у себи. Затим се рекурзивно понавља процес на поддворане док све дворане не постану најмање могуће.

Овај метод резултује лавиринтом са дугим равним зидовима, што олакшава увид у делове лавиринта које треба избегавати.

На пример, у правоугаоном лавиринту, направити, на случајним тачкама, два зида који су нормални један на други. Ова два зида деле велику дворану у четири мање дворане, одвојене са четири зида. Одабрати три од ова четири зида на случајан начин, и отвори рупу величине једне ћелије на случајној позицији у сваком од та три зида. Наставити на исти начин рекурзивно, док свака дворана има величину једне ћелије у било ком смеру.

Једноставни алгоритми

Постоје и другачији алгоритми који захтевају само онолико меморије колико је потребно за чување једне линије 2Д лавиринта или једне равни 3Д лавиринта. Они спречавају петље тако што памте које ћелије у тренутној линији су повезане са ћелијама у претходним линијама, и никада не уклањају зидове између било које две ћелије које су већ повезане.

Већина алгоритама за генерисање лавирината захтева одржавање веза између ћелија, да би се осигурало да ће крајњи резултат бити решив. Валидни једноставно решиви лавиринти могу ипак бити генерисани фокусирањем на сваку ћелију независно. Лавиринт бинарног стабла је стандардни ортогонални лавиринт где свака ћелија увек има пролаз који води лево или горе, али никада обоје. Да би се креирао лавиринт бинарног стабла, за сваку ћелију бацимо новчић и одредимио да ли ће та ћелија имати пролаз који води лево или горе. Увек се узима исти правац за ћелије на границама, и крајњи резултат ће бити валидни једноставно решиви лавиринт који изгледа као бинарно стабло, код ког је горњи леви ћошак његов корен.

Пример кода за генерисање лавиринта написан у програмском језику Python

import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot

def maze(width=81, height=51, complexity=.75, density=.75):
    # Only odd shapes
    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
    # Adjust complexity and density relative to maze size
    complexity = int(complexity * (5 * (shape[0] + shape[1])))
    density    = int(density * (shape[0] // 2 * shape[1] // 2))
    # Build actual maze
    Z = numpy.zeros(shape, dtype=bool)
    # Fill borders
    Z[0, :] = Z[-1, :] = 1
    Z[:, 0] = Z[:, -1] = 1
    # Make isles
    for i in range(density):
        x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
        Z[y, x] = 1
        for j in range(complexity):
            neighbours = []
            if x > 1:             neighbours.append((y, x - 2))
            if x < shape[1] - 2:  neighbours.append((y, x + 2))
            if y > 1:             neighbours.append((y - 2, x))
            if y < shape[0] - 2:  neighbours.append((y + 2, x))
            if len(neighbours):
                y_,x_ = neighbours[rand(0, len(neighbours) - 1)]
                if Z[y_, x_] == 0:
                    Z[y_, x_] = 1
                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
                    x, y = x_, y_
    return Z

pyplot.figure(figsize=(10, 5))
pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')
pyplot.xticks([]), pyplot.yticks([])
pyplot.show()

Види још

Алгоритам за решавање лавиринта

Референце

Спољашње везе

HTML 5 презентација са демонстрацијама алгоритама за генерисање лавиринта
Think Labyrinth: Maze algorithms (Детаљи у вези са описаним и неким другим алгоритмима)
Maze Generation Архивирано на сајту Wayback Machine (28. фебруар 2014) - Master's Thesis (Јава аплет који омогућава корисницима да креирају лавиринт коришћењем различитих алгоритама)
Колекција кодова за генерисање лавирината у различитим програмским језицима
Генерисање и кретање кроз 3Д лавиринт